class Node:
    def __init__(self,val=0,left=None,right=None):
        self.val=val 
        self.left=left
        self.right=right

def dfs(ans, path, root, target):
    if not root: return
    path.append(root.val)
    new_target = target - root.val
    if new_target == 0 and not root.left and not root.right:
        ans.append(path[:])
    dfs(ans, path, root.left, new_target)
    dfs(ans, path, root.right, new_target)
    path.pop()

#这道题和组合总和略有不同，不能直接在参数里传入target-root.val，因为会先判断左或右节点是否为空，若为空就return了，就append不了了，会永远输出空值
#如果先append再return，遍历左右节点又各会append一次，会重复。所以在进入递归以后再append和做减法。

def solve(root, target):  
    ans = []
    dfs(ans, [], root, target)
    return ans

def build_level(lst):
    from collections import deque
    if not lst: return None
    if not lst[0]: return None
    root=Node(lst[0])
    que=deque([root])
    i=1
    n=len(lst)
    while len(que)>0 and i<n:
        cur=que.popleft()
        if i<n and lst[i]: 
            cur.left=Node(lst[i])
            que.append(cur.left)
        if i+1<n and lst[i+1]: 
            if lst[i+1]: cur.right=Node(lst[i+1])
            que.append(cur.right)
        i+=2
    return root

def traversal_pre(root):
    if not root: return []
    return [root.val]+traversal_pre(root.left)+traversal_pre(root.right)

lst=[5,4,8,11,None,13,4,7,2,None,None,5,1]#[8,8,7,9,2,None,None,None,None,4,7,None,None,None,None]
root=build_level(lst)
#print(traversal_pre(root))
print(solve(root,22))